package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 合并区间
 * 2025-02-25 22:12:26
 * 首先把子区间左端点排序
 * 第一个区间直接加入结果集，或者【结果集区间的右边端点】<【待加入区间的左端点】也加入
 * 否则区间有交集的情况下，比较【结果集区间的右边端点】【待加入区间的左端点】谁大取谁
 * O(nlogn)  O(logn)
 */
class MergeIntervals {

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        // 根据区间左端点排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        // 答案
        List<int[]> merged = new ArrayList<>();

        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            // 第一个区间直接加
            // 后续区间和数组区间的最后一个元素作比较 3<4 直接加 (0,3) (4,6)
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                // (0,3) (2,6)
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new MergeIntervals().new Solution();
        int[][] ints = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] merge = solution.merge(ints);
        System.out.println(Arrays.deepToString(merge));
    }
}